package com.example.system.class05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Date 2022/7/23
 * @Created by Jonathan
 * 逆序对问题
 */
public class Code03_ReversePair {
    public static void main(String[] args) {
        int[] arr = new int[]{7, 8, 4, 3};
        final List<int[]> reversePair = getReversePair(arr);
        for (int[] ints : reversePair) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public static List<int[]> getReversePair(int[] arr) {
        List<int[]> ans = new ArrayList<>();
        process(arr, 0, arr.length - 1, ans);
        return ans;
    }

    public static void process(int[] arr, int left, int right, List<int[]> ans) {
        if (left == right) {
            return;
        }
        int middle = left + ((right - left) >> 1);
        process(arr, left, middle, ans);
        process(arr, middle + 1, right, ans);
        merge(arr, left, middle, right, ans);
    }

    private static void merge(int[] arr, int left, int middle, int right, List<int[]> ans) {
        int[] help = new int[right - left + 1];
        int l = left;
        int r = middle + 1;
        int index = 0;
        while (l <= middle && r <= right) {
            // 归并左边的
            if (arr[l] <= arr[r]) {
                help[index++] = arr[l++];
            }
            //  归并右边的
            else {
                // a[l] > arr[r]的
                // 说明a[l...mid] 都是大于arr[r]的
                int mostLeft = l;
                while (mostLeft <= middle) {
                    int[] tmp = new int[]{arr[mostLeft++], arr[r]};
                    ans.add(tmp);
                }
                help[index++] = arr[r++];
            }
        }

        while (l <= middle) {
            help[index++] = arr[l++];
        }

        while (r <= right) {
            help[index++] = arr[r++];
        }

        // 将归并好的还原回去
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }
}
